// https://leetcode.cn/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size(), start = 0;
        while (start < n && cost[start] > gas[start]) start++;
        if (start >= n) return -1;

        while (start < n) {
            int totalGas = 0, totalCost = 0;
            int step = 0;
            while (step < n) {
                totalGas += gas[(start + step) % n];
                totalCost += cost[(start + step) % n];

                if (totalCost > totalGas) {
                    start = start + step + 1;
                    break;
                }
                step++;
            }
            
            if (step == n) return start;
        }
        return -1;
    }
};